package org.yurahome.amazon;

import java.util.AbstractList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

/**
 *
 * @author Yuriy Dunko
 */
public class SinglyLinkedList<T> extends AbstractList<T> implements List<T> {

	class Entry<T> {

		private T value;
		private Entry<T> next;

		public Entry(T value) {
			this.value = value;
		}

		@Override
		public String toString() {
			return String.valueOf(value);
		}
	}

	private Entry<T> first;
	private Entry<T> last;
	private int size;

	@Override
	public boolean add(T element) {
		modCount++;
		if (last == null) {
			first = last = new Entry<T>(element);
		} else {
			last = (last.next = new Entry<T>(element));
		}
		size++;
		return true;
	}

	@Override
	public boolean addAll(Collection<? extends T> collection) {
		return addAll(size, collection);
	}

	@Override
	public boolean addAll(int index, Collection<? extends T> collection) {
		checkBounds(index, false);
		int csize = collection.size();

		if (csize == 0) {
			return false;
		}

		Entry<T> before;
		Entry<T> after = null;

		if (index == size) {
			before = last;
		} else {
			if (index == 0) {
				if (first != null) {
					after = first;
				}
				first = before = null;
			} else {
				before = getEntry(index - 1);
			}

			if (before != null) {
				after = before.next;
			}
		}

		modCount++;

		for (T collectionElement : collection) {
			Entry<T> newEntry = new Entry<T>(collectionElement);
			if (before != null) {
				before.next = newEntry;
				before = newEntry;
			} else {
				first = before = newEntry;
			}
			size++;
		}

		before.next = after;

		if (after == null) {
			last = before;
		}

		return true;
	}

	@Override
	public void add(int index, T element) {
		checkBounds(index, false);

		if (index < size) {
			modCount++;
			Entry<T> newEntry = new Entry<T>(element);

			if (index == 0) {
				newEntry.next = first;
				first = newEntry;
			} else {
				Entry<T> before = getEntry(index - 1);
				newEntry.next = before.next;
				before.next = newEntry;
			}

			if (newEntry.next == null) {
				last = newEntry;
			}

			size++;
		} else {
			add(element);
		}
	}

	@Override
	public void clear() {
		if (size > 0) {
			modCount++;
			first = null;
			last = null;
			size = 0;
		}
	}

	@Override
	public boolean remove(Object element) {
		for (Entry<T> current = first, previous = null; current != null; previous = current, current = current.next) {
			if (current.value == null ? element == null : current.value.equals(element)) {
				modCount++;

				if (previous == null) {
					first = current.next;
				} else {
					previous.next = current.next;
				}

				if (current.next == null) {
					last = previous != null ? previous : first;
				}

				decreaseSize();

				return true;
			}
		}

		return false;
	}

	@Override
	public T remove(int index) {
		checkBounds(index, true);

		Entry<T> previous = null;
		Entry<T> entry = first;

		while (index-- > 0) {
			previous = entry;
			entry = entry.next;
		}

		T element;
		modCount++;

		if (previous == null) {
			element = first.value;
			first = first.next;
		} else {
			element = entry.value;
			previous.next = entry.next;
		}

		if (entry.next == null) {
			last = previous != null ? previous : first;
		}

		decreaseSize();

		return element;
	}

	@Override
	public T get(int i) {
		checkBounds(i, true);
		return getEntry(i).value;
	}

	@Override
	public T set(int index, T newValue) {
		checkBounds(index, true);

		Entry<T> entry = getEntry(index);
		T oldValue = entry.value;
		entry.value = newValue;

		return oldValue;
	}

	@Override
	public int size() {
		return size;
	}

	@Override
	public Iterator<T> iterator() {
		// weak place: could be optimized
		return super.iterator();
	}

	@Override
	public ListIterator<T> listIterator(int index) {
		// weak place: could be optimized
		return super.listIterator(index);
	}

	public void reverseIteratively() {
		if (size < 2) {
			return;
		}

		modCount++;

		last = first;

		for (Entry<T> previous = null, next; true;) {
			next = first.next;
			first.next = previous;
			previous = first;

			if (next == null) {
				return;
			}

			first = next;
		}
	}

	public void reverseRecursive() {
		modCount++;
		last = first;
		first = reverseRecursive(first);
	}

	private Entry<T> reverseRecursive(Entry<T> root) {
		if (root == null || root.next == null) {
			return root;
		}

		Entry<T> next = root.next;

		root.next = null;

		Entry<T> reversed = reverseRecursive(next);

		next.next = root;

		return reversed;
	}

	private void checkBounds(int index, boolean exclusive) {
		if (index < 0 || exclusive ? index >= size : index > size) {
			throw new IndexOutOfBoundsException("Index: " + index + ", Size:" + size);
		}
	}

	private void decreaseSize() {
		size--;
		if (size == 0) {
			last = null;
		}
	}

	private Entry<T> getEntry(int index) {
		Entry<T> entry = first;

		while (index-- > 0) {
			entry = entry.next;
		}

		return entry;
	}
}
